package cn.edu.gdut.test;

import java.util.*;

/**
 * Created by HuGuodong on 2017/11/22.
 */

public class Q730 {
    public static void main(String[] args) {
        subSetSum(4);
    }

    public static void subSetSum(int n){

        Queue q = new ArrayDeque(); //
        Queue q_final = new ArrayDeque(); // 最终得到的queue
        List l = new ArrayList();

        l.add(1);
        q.add(l); // queue初始化，先放一个1

        for(int i=2; i<=n; i++){
            q_final.clear();
            List last_ele = new ArrayList();
            last_ele.add(i);
            q_final.add(last_ele);
            while(!q.isEmpty()){
                Object ele = q.poll();
                q_final.add(ele);
                if (ele instanceof List){
                    List new_ele = new ArrayList();
                    new_ele.addAll((List)ele);
                    new_ele.add(i);
                    q_final.add(new_ele);
                }
            }
            q.clear();
            q.addAll(q_final);
        }

        // 遍历求和
        int sum = 0;
        for (Object ele:
             q_final) {
                for (Object o:
                (List)ele) {
                    sum += (int)o;
                }
        }

        System.out.println("q_final: "+ q_final);
        System.out.println("sum: "+ sum);
    }
}
